1. Technical Field
A “Concurrent Sharing Model” provides a fork-join model of concurrency wherein shared states, data, or variables are conceptually replicated on forks, and only copied or written if necessary, then deterministically merged on joins such that concurrent tasks or programs can work with independent local copies of the shared states, data, or variables in a manner that ensures automated conflict resolution.
2. Related Art
Despite significant research on parallel programming, how to effectively build applications that enable concurrent execution of tasks that perform various functions and may execute asynchronously is not generally well understood. The issue of concurrency is important in practice since a wide range of applications need to be responsive and would benefit from exploiting parallel hardware.
For example, a typical word processing application, where many tasks are executing in parallel, may concurrently run tasks that: (1) save a snapshot of a document to disk, (2) react to keyboard input by a user who is editing the document, (3) perform a spell-check in the background, and (4) exchange document updates with one or more collaborating remote users. Some of these tasks are CPU-bound, others are IO-bound; some only read the shared data, while other tasks may modify the shared data. However, all of the concurrent tasks may potentially access the same data at the same time; thus, these tasks must avoid, negotiate, or any potential read and/or write resolve conflicts.
There has been a significant amount prior work on programming models for concurrency. Recently, many researchers have proposed programming models for deterministic concurrency, creating renewed interest in an old problem previously known as determinacy. These models generally guarantee that the execution is equivalent to some sequential execution, and cannot easily resolve all conflicts on commit. Thus, these types of conventional models operate by restricting tasks from producing such conflicts either statically (by type system) or dynamically (pessimistic with blocking, or optimistic with abort and retry).
The conventional concept of transactional boosting provides coarse-grained transactions, and semantic commutativity, which eliminate false conflicts by raising the abstraction level. Unfortunately, while transactional boosting avoids false conflicts, it is not capable of resolving true conflicts deterministically (in a not necessarily serializable way).
As is well known to those skilled in the art, traditional “locking” schemes are appropriate for safely sharing data between tasks. However, locking complicates the code because it requires programmers to think about the placement of critical sections, which involves nontrivial tradeoffs and complicates code maintenance. Moreover, locking alone does not always suffice. For example, consider a game application which executes concurrently (1) a physics task which updates the position of all game objects based on their speed and the time elapsed, and (2) a render task which draws all objects onto the screen. Then, any solution based solely on locks would either hamper concurrency (too coarse) or provide insufficient isolation (too fine), as some of the objects may be rendered at the future position, while others are rendered at the current position.
For this reason, replication is often a necessary ingredient to achieve parallelization of application tasks. Games, for example, may maintain two copies of the shared state (using so-called double-buffering) to guarantee isolation of tasks while enabling any number of read-only tasks to execute concurrently with a single writer task. However, this pattern is somewhat specific to the synchronization structure of games, and maintaining just two buffers is not always enough (for example, there may be multiple concurrent modifications, or snapshots may need to persist for more than a single frame). Moreover, performing a full replication of the shared state is not the most space-efficient solution.
Another common replication-based solution is to use immutable objects to encode shared states. Any tasks that wish to modify an immutable object must instead create a copy. This pattern can efficiently guarantee isolation and enables concurrency. However, it can introduce new challenges, such as how to resolve conflicting updates, or how to bound space requirements in situations where frequent modifications to the data may cause excessive copying.
Conventional “transactions” or “transactional memory” are used in an attempt to address the problem of handling concurrent access to shared data. However, transactions (whether optimistic or pessimistic) handle conflicts non-deterministically. Conventionally, it has long been recognized that providing strong guarantees such as serializability or linearizability can be overly conservative for some applications. Consequently, users of “transactions” have proposed alternate guarantees such as “multi-version concurrency control” or “snapshot isolation” (SI). SI transactions operate on stable snapshots and do not guarantee serializability. Unfortunately, they are restricted by being unable to perform deterministic conflict resolution (but rather abort transactions in schedule-dependent and thus nondeterministic ways) and do not support general nesting of transactions. Further, optimistic transactions do not fare well in the presence of conflicts that cause excessive rollback and retry. Moreover, combining optimistic transactions with I/O can be done only under some restrictions because the latter cannot always be rolled back.
Recently, researchers have proposed programming models for deterministic concurrency. However, these models are quite restrictive in that because they guarantee task execution is equivalent to some sequential execution, they cannot easily resolve all conflicts on commit, and must therefore restrict tasks from producing such conflicts either statically (by type system) or dynamically (pessimistic with blocking, or optimistic with abort and retry). Also, some of these models allow only a restricted “fork-join” form of concurrency. Hardware architects have also proposed supporting deterministic execution. However, these mechanisms guarantee determinism only, not isolation.
Cilk++ is a general-purpose programming language designed for multithreaded parallel computing. Cilk++ hyperobjects are primitives that use type declarations by the programmer to change the semantics of shared variables. Cilk++ hyperobjects may split, hold, and reduce values. However, these primitives do not provide seamless semantics that ensure determinacy on joins. In particular, the determinacy guarantees are fragile, i.e., they do not hold for all programs.
Some languages statically restrict the use of joins, to make stronger scheduling guarantees (as done in Cilk++) or to simplify the most common usage patterns and to eliminate common user mistakes (as done in X10). In fact, many models use a restricted “fork-join” parallelism. Unfortunately, such restrictions (while reasonable for data-parallel problems) can make it difficult to write applications that adapt to external non-determinism or to unpredictable latencies.